/*
 * This is a simple C++ implementation of the least recently used (LRU) cache. 
 *
 *
 */


#include <list>
#include <vector>
#ifdef __GNUC__
#include <ext/hash_map>
#else
#include <hash_map>
#endif

using namespace __gnu_cxx;

template <typename Key, typename Value> 
class lru_cache {
	private:
		// The main storage of the LRU cache - a doubly linked list with each node as a pair
		// of key and value.
		typedef std::list<std::pair<Key, Value> > _kv_store;
		_kv_store cache_list;

	public:
		typedef typename _kv_store::iterator iterator;
		typedef typename _kv_store::const_iterator const_iterator;

		typedef typename _kv_store::size_type size_type;
		typedef typename _kv_store::difference_type difference_type;
		typedef typename _kv_store::pointer pointer;
		typedef typename _kv_store::const_pointer const_pointer;
		typedef typename _kv_store::reference reference;
		typedef typename _kv_store::const_reference const_reference;
	
	private:
		// A hash map that maps the key to the list iterator.
		typedef stdext::hash_map<Key, iterator> _ki_map;
		_ki_map key_iterator_map;			
		typedef stdext::hash_map<Key, iterator>::iterator _map_iterator;
		const int DEFAULT_SIZE = 1024;
		unsigned int _max_size, _curr_size;
	
	public:
		// Constructors
		lru_cache():_max_size(DEFAULT_SIZE),_curr_size(0) {}
		lru_cache(const unsigned int sz):_max_size(sz), _curr_size(0) {}
		
		// Destructor
		~lru_cache() { destroy(); }	


		size_type const unsigned int size() const { return _curr_size; }	

		size_type const unsigned int max_size() const { return _max_size; }

		// Clear memory
		void destroy() {
			cache_list.clear();	
			key_iterator_map.clear();
			_curr_size = 0;
		}	

		iterator begin() { return cache_list.begin(); }	
		const_iterator begin() const { return cache_list.begin(); } 
		iterator end() { return cache_list.end(); }
		const_iterator end() const { return cache_list.end(); }
		bool empty() const { return cache_list.empty(); }
		bool exists(const Key k) const { 
			return key_iterator_map.find(k) != key_iterator_map.end(); 
		}	

		
		void remove(Key k) {
			iterator it = key_iterator_map.find(k);
			remove_internal(it);
		}

		void remove_internal(iterator it) {
			cache_list.erase(it->second);
			key_iterator_map.erase(it);
		}	

		void insert(const Key& k, const Value& v) {
			_map_iterator it = update(k);				
			if(it it != key_iterator_map.end())
				remove_internal(it)
			// Now insert the node at the front of the cache
			cache_list.push_front(std::make_pair(k, v));
			iterator iter = cache_list.begin();
			// Put the iterator of the new node into the hash map
			key_iterator_map[k] = iter;
			// update current size
			_curr_size++;
			if(_curr_size > _max_size) {
				iter = cache_list.end();
				remove(iter->first);	
			} 	
		}
	

		bool get(const Key& k, Value& v) {
			map_iterator it = key_iterator_map.find(k);
			if(it == 	key_iterator_map.end())
				return false;
			v = it->second->second;
			return true;
		}

		Value& operator[](const Key& k){ 
			map_iterator it = key_iterator_map.find(k);
			if(it == key_iterator_map.end()) {
				// The key doesn't exist, do insert
				insert(k, Value()); // Insert a default value 
				return cache_list.begin();		
			}	
			else {
				// Return the value
				return it->second->second;			
			}				
		}	
		
	private:
		_map_iterator update(const Key& k) {
			_map_iterator it = key_iterator_map.find(k);
			if(k == key_map_iterator.end()) return it;
			cache_list.splice(cache_list.begin(), cache_list, it->second);	
			return it;
		}
		
}
	

